package offer.offer55;

/**
 * @Author: wjy
 * @Date: 2021/11/4 9:17
 */
public class Solution {

    public static void main(String[] args) {

/*        TreeNode treeNode1 = new TreeNode(15);
        TreeNode treeNode2 = new TreeNode(7);
        TreeNode treeNode3 = new TreeNode(20);
        treeNode3.left = treeNode1;
        treeNode3.right = treeNode2;
        TreeNode treeNode4 = new TreeNode(9);
        TreeNode treeNode5 = new TreeNode(3);
        treeNode5.left = treeNode4;
        treeNode5.right = treeNode3;*/

        TreeNode treeNode1 = new TreeNode(4);
        TreeNode treeNode2 = new TreeNode(4);
        TreeNode treeNode3 = new TreeNode(3);
        treeNode3.left = treeNode1;
        treeNode3.right = treeNode2;
        TreeNode treeNode4 = new TreeNode(3);
        TreeNode treeNode5 = new TreeNode(2);
        treeNode5.left = treeNode3;
        treeNode5.right = treeNode4;
        TreeNode treeNode6 = new TreeNode(2);
        TreeNode treeNode7 = new TreeNode(1);
        treeNode7.left = treeNode5;
        treeNode7.right = treeNode6;

/*        TreeNode treeNode1 = new TreeNode(4);
        TreeNode treeNode3 = new TreeNode(4);
        treeNode3.right = treeNode1;
        TreeNode treeNode5 = new TreeNode(3);
        treeNode5.left = treeNode3;
        TreeNode treeNode6 = new TreeNode(2);
        TreeNode treeNode4 = new TreeNode(2);
        TreeNode treeNode2 = new TreeNode(3);
        treeNode4.left = treeNode2;
        TreeNode treeNode7 = new TreeNode(1);
        treeNode6.right = treeNode5;
        treeNode7.left = treeNode4;
        treeNode7.right = treeNode6;*/

        Solution solution = new Solution();
        System.out.println(solution.isBalanced(treeNode7));

    }

    boolean flag = true;

    /**
     * 思路：递归＋回溯
     * 1.先遍历左子树再遍历右子树
     * 2.如果是该节点为叶子节点，返回count(初始值为1，自底向上递增1)
     * 3.如果左右子树返回值相减大于1则证明该树非AVL树
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {

        this.level(root);

        return flag;
    }

    public int level(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int count = 1;
        int levelLeft = this.level(node.left);
        int levelRight = this.level(node.right);
        count += Math.max(levelLeft, levelRight);

        if (Math.abs(levelLeft - levelRight) > 1) {
            flag =false;
        }

        return count;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}